1. Field of the Invention
The present invention relates to Asynchronous Transfer Mode (ATM) networks, and more particularly, to methods and systems for congestion avoidance in ATM backbone networks.
2. Background of the Art
A communications network generally includes a plurality of nodes interconnected by transmission links (or xe2x80x9clinksxe2x80x9d), which are defined by a specific bandwidth (or capacity). In an ATM network, a source node transmits data in the form of fixed sized cells to a destination node through a connection (referred to as a virtual circuit), which is established between the source node and the destination node. The virtual circuit may traverse zero or more nodes (i.e., switches) between the source node and the destination node. A group of virtual circuits between the source node and the destination node is referred to as a virtual path. The cells may include any type of digitized information, including audio, computer data, video, multimedia, Internet data, etc.
In an ATM backbone network, source nodes receive traffic from one or more external access networks. To control congestion in the network, the network uses a Connection Admission Control (CAC) method to determine the resources that are required to satisfy the quality of service (QoS) requirements of the virtual circuit associated with the traffic, and if the determined resources are available, to reserve the resources for that virtual circuit.
When a source node receives traffic from an external access network, the source node negotiates a traffic contract with the network, where the traffic contract includes the necessary information for determining the required resources to establish a virtual circuit in the network. Specifically, the traffic contract includes a traffic descriptor and QoS requirements. The traffic descriptor further includes a source traffic descriptor and a cell delay variation tolerance (CDVT). The parameters of the source traffic descriptor are typically peak cell rate (PCR), average or sustainable cell rate (SCR), and the maximum burst sizes (MBS).
Generally, the existing ATM networks use a variety of proprietary methods (known as the equivalent bandwidth methods) to determine the amount of bandwidth that the networks must reserve in order to satisfy the QoS requirements of the virtual circuits associated with the traffic. Once a network determines the required bandwidth, the network then determines if a virtual path in the network has sufficient bandwidth to accommodate the virtual circuit. If the network identifies such a virtual path, the network reserves the determined bandwidth on the links that support the virtual path. If the network cannot identify such a virtual path, the network rejects the traffic.
An ATM network typically reserves the required bandwidth for the entire duration of a virtual circuit associated with a traffic stream. Because the duration of a virtual circuit is substantially longer than the sum of the durations of the individual bursts in the traffic stream, the virtual circuit does not use the reserved bandwidth during the silent periods between bursts, and thus, resulting in an inefficient use of bandwidth for bursty traffic.
One known solution to the inefficient use of bandwidth for bursty traffic is to reserve the required bandwidth only for the duration of the individual bursts instead of the duration of the virtual circuit. Specifically, ITU-T Rec. I.371, xe2x80x9cTraffic Control And Congestion Control In B-ISDN,xe2x80x9d Perth, U.K. Nov. 6-14, 1995, discloses a burst level reservation method known as the ABT method. In this method, the block of cells in each burst is enclosed by special management cells (referred to as RM cells), which identify the beginning and the end of each burst, respectively. An RM cell identifies the bandwidth that is required to transport the burst within the network.
There are two types of ABT methods namely, ABT with delay transmission (ABT/DT) and ABT with immediate transmission (ABT/IT). In a network that uses the ABT/DT method, when a source node receives a burst from an external access network, the source node sends an RM cell to the ATM network, requesting permission to admit the burst into the network. The source node then waits for an admission or a rejection notification from the network. The network determines whether it has the required bandwidth available to satisfy the QoS of the virtual circuit associated with the burst, and if so, the network reserves the required bandwidth for that virtual circuit and sends an admission notification to the source node. When the source node receives the admission notification, the source node admits the burst into the network. However, if the network determines that it does not have the required bandwidth available, the network sends a rejection notification to the source node.
In a network that uses the ABT/IT method, when a source node receives a burst from an external access network, the source node immediately admits the burst into the network without reserving the required bandwidth to transport the burst in the network. As a result, after admitting the burst into the network, if any link associated with the virtual circuit of the admitted burst does not have the required bandwidth available to transport the burst, the network discards the burst.
One disadvantage of the ABT/DT method is that in wide area networks, due to long propagation delays between nodes in the network, the process of determining and reserving the required bandwidth for each burst can be prohibitively long compared to the duration of the individual bursts and the burst inter-arrival times. The ABT/IT method, on the other hand, may exacerbate congestion in an already congested network by admitting bursts into the network, when the network does not have the required bandwidth to transport the bursts.
Thus, it is desirable to have a method and system for addressing the above and other disadvantages of the existing congestion control avoidance methods for bursty traffic in ATM networks.
Methods and systems consistent with the present invention control congestion in an ATM network by pre-allocating for a pre-determined interval of time a set of burst access parameters to a set of pre-allocated virtual paths between a set of source node and destination node pairs in the ATM network, and controlling, at the burst level, the traffic at each source node based on the pre-allocated set of burst access parameters and without communicating with other nodes in the ATM network. Specifically, the network pre-allocates, for a pre-determined interval of time, a set of virtual paths between each source-destination node pair in the network, pre-allocates a set of maximum permitted rates to the pre-allocated set of virtual paths, respectively, and pre-assigns a set of burst access thresholds to a set of service classes, respectively, in the pre-allocated virtual paths, where the pre-assigned burst access thresholds are less than or equal to the corresponding pre-allocated maximum permitted rates.
Each source node in the network then controls, at the burst level, the traffic directed to the source node based on the pre-allocated set of maximum permitted rates and the pre-assigned set of burst access thresholds and without communicating with other nodes in the network. Specifically, each source node detects the beginning of a burst in the traffic that is directed to that source node. From among the pre-allocated set of virtual paths between the source-destination node pair, the source node identifies a pre-allocated virtual path associated with the detected burst. The source node then identifies the service class of the detected burst, and the burst access threshold that corresponds to the identified service class. The source node admits the detected burst onto the identified pre-allocated virtual path when a total reserved peak cell rate for all bursts that are in progress in the identified pre-allocated virtual path plus a peak cell rate of the detected burst is less than the identified burst access threshold. Otherwise, the source node rejects the detected burst from the network.
Methods and systems consistent with the present invention provide a facility for engineering a set of burst access parameters, subject to network capacity, burst rejection quality of service requirements, and conservation flow constraints, such that a total weighted rate of burst rejections in a network is minimized. Specifically, the network computes a set of maximum permitted rates for each pre-allocated virtual path in the network. Based on the computed maximum permitted rates, the network computes estimated offered loads associated with each service class in each pre-allocated virtual path. Furthermore, based on the computed set of maximum permitted rates and the computed set of estimated offered loads, the network computes a set of burst access thresholds.